package lanQiaoBei.数据结构.堆;

import java.io.*;

/*
 * 模拟复杂堆
 * 维护一个集合，初始时集合为空，支持如下操作
 * I x 插入一个数x;
 * PM 输出当前集合中的最小值;
 * DM 删除当前集合的最小值;
 * D k 删除当前集合中的第k个插入数;
 * C k x 将当前集合第k个插入的数修改为x;
 *
 * 输入格式：
 * 输入一个整数n;
 * 接下来n行为操作
 * */
public class P1 {
    final static int N = 100010;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, size,idx;
    static int[] h = new int[N],ph=new int[N],hp=new int[N];//ph[k]表示第k个插入的下标 hp[i]表示i下标的数对应的是第几个插入的数

    static void swap(int i, int j,int[] a) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static void up(int i) {
        while (i / 2 > 0 && h[i] < h[(i / 2)]) {
            heap_swap(i, i / 2);
            i = i / 2;
        }
    }

    static void down(int i) {
        int t = i, l = 2 * i, r = l + 1;
        if (l <= size && h[l] < h[t]) t = l;
        if (r <= size && h[r] < h[t]) t = r;
        if (t != i) {
            heap_swap(i, t);
            down(t);
        }
    }
    static void heap_swap(int i,int j){
           swap(i,j,h);
           swap(hp[i],hp[j],ph);
           swap(i,j,hp);
    }
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String[] ss = br.readLine().split(" ");
            if ("I".equals(ss[0])) {
                h[++size] = Integer.parseInt(ss[1]);
                ph[++idx]=size;hp[size]=idx;
                up(size);
            } else if ("PM".equals(ss[0])) {
                System.out.println(h[1]);
            } else if ("DM".equals(ss[0])) {
                heap_swap(1, size--);
                down(1);
            } else if ("D".equals(ss[0])) {
                int k = Integer.parseInt(ss[1]);
                heap_swap(ph[k],size--);
                down(ph[k]);up(ph[k]);
            } else{
                int k=Integer.parseInt(ss[1]),x=Integer.parseInt(ss[2]);
                h[ph[k]]=x;
                down(ph[k]);up(ph[k]);
            }
        }
    }
}
